package sort;

import java.util.Arrays;

public class InsertSort {

    //不需要进行完整的交换，只需要把元素暂存起来，再把有序区的元素从前向后逐一复制
    //插入排序
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //暂存元素
            int insertValue = array[i];
            int j = i - 1;
            //从右往左比较元素的同时进行元素复制
            for (;(j >= 0) && (insertValue < array[j]); j--) {
                array[j + 1] = array[j];
            }
            //insertValue的值插入适当位置
            array[j + 1] = insertValue;
        }
    }

    public static void main(String[] args) {
        int[] array = {12,3,4,1,9,7,6};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }

}
